#include "binary_tree.h"

#include <concepts>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include "log.h"

namespace DataStructure {
namespace {
template<typename T>
concept Printable = requires(T t, std::ostream& os) {
    os << t;
};

template<Printable T>
void PrintVectorData(const std::vector<T> &data)
{
    std::ostringstream oss;
    for (const auto &element : data) {
        oss << element << " ";
    }
    SYS_LOG(_DEBUG) << oss.str() << '\n';
}
} // namespace
BinaryTree::BinaryTree() : root_(nullptr)
{}

BinaryTree::~BinaryTree()
{
    Clear(root_);
}

void BinaryTree::Clear(TreeNode* node)
{
    if (node) {
        Clear(node->left_);
        Clear(node->right_);
        delete node;
    }
}

void BinaryTree::Insert(int32_t val)
{
    if (root_ == nullptr) {
        root_ = new TreeNode(val);
        return;
    }

    std::queue<TreeNode*> q;
    q.push(root_);
    while(!q.empty()) {
        TreeNode* current = q.front();
        q.pop();

        if (current->left_ == nullptr) {
            current->left_ = new TreeNode(val);
            return;
        } else {
            q.push(current->left_);
        }

        if (current->right_ == nullptr) {
            current->right_ = new TreeNode(val);
            return;
        } else {
            q.push(current->right_);
        }
    }
}

void BinaryTree::PreOrderRecursion()
{
    std::vector<int32_t> result;
    PreOrderRecursionInner(root_, result);
    PrintVectorData<int32_t>(result);
}

void BinaryTree::PreOrderRecursionInner(TreeNode* node, std::vector<int32_t> &result)
{
    if (node == nullptr) {
        return;
    }
    result.emplace_back(node->val_);
    PreOrderRecursionInner(node->left_, result);
    PreOrderRecursionInner(node->right_, result);
}

void BinaryTree::InOrderRecursion()
{
    std::vector<int32_t> result;
    InOrderRecursionInner(root_, result);
    PrintVectorData<int32_t>(result);
}

void BinaryTree::InOrderRecursionInner(TreeNode* node, std::vector<int32_t> &result)
{
    if (node == nullptr) {
        return;
    }
    InOrderRecursionInner(node->left_, result);
    result.emplace_back(node->val_);
    InOrderRecursionInner(node->right_, result);
}

void BinaryTree::PostOrderRecursion()
{
    std::vector<int32_t> result;
    PostOrderRecursionInner(root_, result);
    PrintVectorData<int32_t>(result);
}

void BinaryTree::PostOrderRecursionInner(TreeNode* node, std::vector<int32_t> &result)
{
    if (node == nullptr) {
        return;
    }
    PostOrderRecursionInner(node->left_, result);
    PostOrderRecursionInner(node->right_, result);
    result.emplace_back(node->val_);
}

void BinaryTree::PreOrderIterative()
{
    if (root_ == nullptr) {
        return;
    }

    std::vector<int32_t> result;
    std::stack<TreeNode*> stk;
    stk.push(root_);

    while (!stk.empty()) {
        TreeNode* current = stk.top();
        stk.pop();
        result.emplace_back(current->val_);

        if (current->right_ != nullptr) {
            stk.push(current->right_);
        }
        if (current->left_ != nullptr) {
            stk.push(current->left_);
        }
    }
    PrintVectorData<int32_t>(result);
}

TreeNode* BinaryTree::SearchNode(int32_t val) const
{
    return SearchNodeInner(root_, val);
}

TreeNode* BinaryTree::SearchNodeInner(TreeNode* node, int32_t val) const
{
    if (node == nullptr || node->val_ == val) {
        return node;
    }

    TreeNode* leftResult = SearchNodeInner(node->left_, val);
    if (leftResult != nullptr) {
        return leftResult;
    }
    return SearchNodeInner(node->right_, val);
}

int32_t BinaryTree::GetHeight()
{
    return GetHeightInner(root_);
}

int32_t BinaryTree::GetHeightInner(TreeNode* node)
{
    if (node == nullptr) {
        return 0;
    }
    auto leftHeight = GetHeightInner(node->left_);
    auto rightHeight = GetHeightInner(node->right_);
    return std::max(leftHeight, rightHeight) + 1;
}

int32_t BinaryTree::GetSize()
{
    return GetSizeInner(root_);
}

int32_t BinaryTree::GetSizeInner(TreeNode* node)
{
    if (node == nullptr) {
        return 0;
    }
    return GetSizeInner(node->left_) + GetSizeInner(node->right_) + 1;
}

TreeNode* BinaryTree::GetRoot() const
{
    return root_;
}
void BinaryTree::SetRoot(TreeNode* node)
{
    root_ = node;
}
} // namespace DataStructure